package backtrackStudy;

import java.util.LinkedList;
import java.util.List;

public class BacktraceStudy09 {

    private static List<List<Integer>> res = new LinkedList<>();

    /**
     * LeetCode T78 子集
     * 给你一个整数数组 nums ，数组中的元素 互不相同 。返回该数组所有可能的子集（幂集）。
     *
     * 解集 不能 包含重复的子集。你可以按 任意顺序 返回解集。
     * @param args
     */
    public static void main(String[] args) {
        int[] nums = new int[]{1,2,3};
        List<List<Integer>> subsets = subsets(nums);
    }

    //方法一：暴力枚举
    public static List<List<Integer>> subsets(int[] nums){
        List<List<Integer>> ans = new LinkedList<>();
        int len = nums.length;
        for (int i = 0; i < (1<<len); i++){
            List<Integer> list = new LinkedList<>();
            //判断1的位置
            for (int j = 0; j < len; j++){
                int temp = (i>>j)&1;
                if (temp == 1){
                    list.add(nums[j]);
                }
            }
            ans.add(list);
        }
        return ans;
    }
    //方法二：回溯法
    public static List<List<Integer>> subsets2(int[] nums){
        //记录路径
        LinkedList<Integer> trace = new LinkedList<>();
        backtrace(nums, 0, trace);
        return res;

    }

    //进行回溯，首先确定返回值和参数列表
    public static void backtrace(int[] nums, int beginIndex, LinkedList<Integer> trace){
        //收集数据
        res.add(new LinkedList<>(trace));
        //定义出口
        if (beginIndex >= nums.length){
            return;
        }

        //定义循环体
        for (int i = beginIndex; i < nums.length; i++){
            //选择
            trace.add(nums[i]);
            backtrace(nums, i+1, trace);
            //取消选择
            trace.removeLast();
        }
    }
}
